/**
 * Interface for Binary Search Trees (BST)
 * @author Gilberto Gaxiola
 */
public interface BinarySearchTree<K extends Comparable<K>> {
	
	/**
	 * Returns the root node of the tree, or null if none.
	 * @return a BinaryNode or null
	 */
	public BinaryNode<K> getRoot();
	
	/**
	 * Is this an empty tree?
	 * @return true if so, false if not
	 */
	public boolean isEmpty();
	
	/**
	 * Inserts a new value into the tree.
	 * @param c value to insert Remember that this value is just the raw data.
	 * You must encapsulate it in a BinaryNode
	 */
	public BSTNode<K> insert(BSTNode<K> parent, K c, boolean left, boolean dup);
	
	/**
	 * Look up an element in the tree.
	 * If an object which is equal (i.e., compareTo is 0) 
	 * exists in the tree, we return that object. Otherwise, we return null.
	 * @param c value to find
	 * @return the element in the tree, or null
	 */
	public BinaryNode<K> find(K c);
	
	/**
	 * Remove an element in the tree.
	 * REALLY IMPORTANT: You will need to use the 3-Case Successor approach.
	 * For details on the 3-Case Successor please check the Homework write up (doc file)
	 * @param c value to remove
	 * @return true if the values was removed, false otherwise
	 */
	public boolean remove(K c);
	
	public void setRoot(BSTNode<K> root);
}
